package com.wyx.suanfa;

/**
 * @author 王艺锡
 * @version 1.0
 */
public class numIslands {
    //给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
    //
    //岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
    //
    //此外，你可以假设该网格的四条边均被水包围。
    //
    //
    public static void main(String[] args) {



    }
}
/*
深搜
* class Solution {
    public int numIslands(char[][] grid) {
        int res = 0;//记录岛屿个数

        for(int i = 0;i<grid.length;i++){
            for(int j = 0;j<grid[0].length;j++){
                //如果找到了岛屿
                if(grid[i][j] == '1'){
                    res++;
                    //将当前岛屿的所有陆地节点都改为'0'
                    dfs(grid,i,j);
                }

            }
        }
        return res;
    }


   void dfs(char[][] grid,int x,int y){
        //如果越界或者遍历到海
        if(x <0 || x == grid.length || y < 0 || y == grid[0].length || grid[x][y] == '0'){
            return;
        }
        //将当前陆地节点淹没为海
        grid[x][y] = '0';
        dfs(grid,x,y + 1);
        dfs(grid,x,y - 1);
        dfs(grid,x + 1,y);
        dfs(grid,x - 1,y);
    }
}*/


/*
*
* //广搜
    class Solution {
    boolean[][] visited;
    int[][] move = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public int numIslands(char[][] grid) {
        int res = 0;
        visited = new boolean[grid.length][grid[0].length];
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                if(!visited[i][j] && grid[i][j] == '1') {
                    bfs(grid, i, j);
                    res++;
                }
            }
        }
        return res;
    }

    //将这片岛屿上的所有陆地都访问到
    public void bfs(char[][] grid, int y, int x) {
        Deque<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{y, x});
        visited[y][x] = true;
        while(!queue.isEmpty()) {
            int[] cur = queue.poll();
            int m = cur[0];
            int n = cur[1];
            for(int i = 0; i < 4; i++) {
                int nexty = m + move[i][0];
                int nextx = n + move[i][1];
                if(nextx < 0 || nexty == grid.length || nexty < 0 || nextx == grid[0].length) continue;
                if(!visited[nexty][nextx] && grid[nexty][nextx] == '1') {
                    queue.offer(new int[]{nexty, nextx});
                    visited[nexty][nextx] = true; //只要加入队列就标记为访问
                }
            }
        }
    }
}*/